Efficient allocation of network resources, such as available network bandwidth, has become critical as enterprises increase reliance on distributed computing environments and wide area computer networks to accomplish critical tasks. The widely-used TCP/IP protocol suite, which implements the world-wide data communications network environment called the Internet and is employed in many local area networks, omits any explicit supervisory function over the rate of data transport over the various devices that comprise the network. While there are certain perceived advantages, this characteristic has the consequence of juxtaposing very high-speed packets and very low-speed packets in potential conflict and produces certain inefficiencies. Certain loading conditions degrade performance of networked applications and can even cause instabilities which could lead to overloads that could stop data transfer temporarily.
In order to understand the context of certain embodiments of the invention, the following provides an explanation of certain technical aspects of a packet based telecommunications network environment. Internet/Intranet technology is based largely on the TCP/IP protocol suite. At the network level, IP provides a “datagram” delivery service—that is, IP is a protocol allowing for delivery of a datagram or packet between two hosts. By contrast, TCP provides a transport level service on top of the datagram service allowing for guaranteed delivery of a byte stream between two IP hosts. In other words, TCP is responsible for ensuring at the transmitting host that message data is divided into packets to be sent, and for reassembling, at the receiving host, the packets back into the complete message.
TCP has “flow control” mechanisms operative at the end stations only to limit the rate at which a TCP endpoint will emit data, but it does not employ explicit data rate control. The basic flow control mechanism is a “sliding window”, a window which by its sliding operation essentially limits the amount of unacknowledged transmit data that a transmitter is allowed to emit. Another flow control mechanism is a congestion window, which is a refinement of the sliding window scheme involving a conservative expansion to make use of the full, allowable window.
The sliding window flow control mechanism works in conjunction with the Retransmit Timeout Mechanism (RTO), which is a timeout to prompt a retransmission of unacknowledged data. The timeout length is based on a running average of the Round Trip Time (RTT) for acknowledgment receipt, i.e. if an acknowledgment is not received within (typically) the smoothed RTT+4*mean deviation, then packet loss is inferred and the data pending acknowledgment is re-transmitted. Data rate flow control mechanisms which are operative end-to-end without explicit data rate control draw a strong inference of congestion from packet loss (inferred, typically, by RTO). TCP end systems, for example, will “back-off,”—i.e., inhibit transmission in increasing multiples of the base RTT average as a reaction to consecutive packet loss.
A crude form of bandwidth management in TCP/IP networks (that is, policies operable to allocate available bandwidth from a single logical link to network flows) is accomplished by a combination of TCP end systems and routers which queue packets and discard packets when some congestion threshold is exceeded. The discarded and therefore unacknowledged packet serves as a feedback mechanism to the TCP transmitter. Routers support various queuing options to provide for some level of bandwidth management. These options generally provide a rough ability to partition and prioritize separate classes of traffic. However, configuring these queuing options with any precision or without side effects is in fact very difficult, and in some cases, not possible. Seemingly simple things, such as the length of the queue, have a profound effect on traffic characteristics. Discarding packets as a feedback mechanism to TCP end systems may cause large, uneven delays perceptible to interactive users. Moreover, while routers can slow down inbound network traffic by dropping packets as a feedback mechanism to a TCP transmitter, this method often results in retransmission of data packets, wasting network traffic and, especially, inbound capacity of a WAN link. In addition, routers can only explicitly control outbound traffic and cannot prevent inbound traffic from over-utilizing a WAN link. A 5% load or less on outbound traffic can correspond to a 100% load on inbound traffic, due to the typical imbalance between an outbound stream of acknowledgments and an inbound stream of data.
In response, certain data flow rate control mechanisms have been developed to provide a means to control and optimize efficiency of data transfer as well as allocate available bandwidth among a variety of business enterprise functionalities. For example, U.S. Pat. No. 6,038,216 discloses a method for explicit data rate control in a packet-based network environment without data rate supervision. Data rate control directly moderates the rate of data transmission from a sending host, resulting in just-in-time data transmission to control inbound traffic and reduce the inefficiencies associated with dropped packets. Bandwidth management devices allow for explicit data rate control for flows associated with a particular traffic type. For example, U.S. Pat. No. 6,046,980 discloses systems and methods allowing for application layer control of bandwidth utilization in packet-based computer networks. For example, bandwidth management devices allow network administrators to specify policies operative to control and/or prioritize the bandwidth allocated to individual data flows according to traffic classifications. In addition, certain bandwidth management devices, as well as certain routers, allow network administrators to specify aggregate bandwidth utilization controls to divide available bandwidth into partitions. With some network devices, these partitions can be configured to ensure a minimum bandwidth and/or cap bandwidth as to a particular class of traffic. An administrator specifies a traffic class (such as FTP data, or data flows involving a specific user) and the size of the reserved virtual link—i.e., minimum guaranteed bandwidth and/or maximum bandwidth. Such partitions can be applied on a per-application basis (protecting and/or capping bandwidth for all traffic associated with an application) or a per-user basis (protecting and/or capping bandwidth for a particular user). In addition, certain bandwidth management devices allow administrators to define a partition hierarchy by configuring one or more partitions dividing the access link and further dividing the parent partitions into one or more child partitions.
To facilitate the implementation, configuration and management tasks associated with bandwidth management and other network devices including traffic classification functionality, various traffic classification configuration models and data structures have been implemented. For example, various routers allow network administrators to configure access control lists (ACLs) consisting of an ordered set of access control entries (ACEs). Each ACE contains a number of fields that are matched against the attributes of a packet entering or exiting a given interface. In addition, each ACE has an associated action that indicates what the routing system should do with the packet when a match occurs. ACLs can be configured to accomplish or facilitate a variety of tasks, such as security, redirection, caching, encryption, network address translation, and policy routing. Once configured by an administrator, the routing system compiles the ACL into a hash table to expedite the took up process during operation of the system.
As discussed in the above-identified patents and patent applications, identification of traffic types associated with data flows traversing an access link involves the application of matching criteria to various characteristics of the data flows. Such matching criteria can include source and destination IP addresses, port numbers, MIME types, application-specific attributes in packet payloads, etc. After identification of a traffic type corresponding to a data flow, a bandwidth management device can associate and subsequently apply a bandwidth utilization control (e.g., a policy or partition) to the data flow. Accordingly, a traffic class to be useful for controlling network bandwidth, or simply for monitoring bandwidth usage, should generally correspond to network traffic types commonly found traversing modern networks. Useful traffic classes include network traffic associated with different applications, such as Citrix®, database applications, accounting applications, email, file transfer, web browsing, and the like. The configuration of such traffic classes, however, requires detailed knowledge of the technical aspects or characteristics of each kind of network traffic (such as protocol identifiers, port numbers, etc.) in order to configure these traffic classes. Configuration of such traffic classes, however, can be quite complex and time-consuming, and often requires an extensive knowledge base of known network traffic types beyond the purview of a typical network administrator.
To that end, U.S. Pat. No. 6,412,000 discloses methods for automatically classifying network traffic based upon information gathered from multiple layers in a multi-layer protocol network. The method disclosed in this patent allows for a network traffic monitoring system that analyzes real traffic traversing a given network and automatically produces a list of “found” or “discovered” traffic. These technologies allow network administrators to install a network appliance at a strategic point in the network, for example, and run it to automatically discover what new applications may be present on the network. In addition, U.S. Pat. Nos. 6,412,000 and 6,457,051 disclose methods and system that automatically classify network traffic according to a set of classification attributes. As these patents teach, the traffic classification configuration can be arranged in a hierarchy, where classification of a particular packet or data flow traverses a network traffic classification tree until a matching leaf traffic class, if any, is found. Such prior art classification trees are data structures reflecting the hierarchical aspect of traffic class relationships, wherein each node of the tree represents a traffic class and includes a set of attributes or matching rules characterizing the traffic class. The traffic classification, at each level of the hierarchy, determines whether the data flow or packet matches the attributes of a given traffic class node and, if so, continues the process for child traffic class nodes down to the leaf nodes. In certain modes, unmatched data flows map to a default traffic class. Furthermore, as U.S. Pat. No. 6,591,299 teaches, newly discovered traffic types or classes are added to the traffic classification hierarchy. In addition, U.S. patent application Ser. No. 09/198,051, incorporated by reference herein, discloses automatic assignment of bandwidth utilization controls for discovered traffic classes.
The automatic traffic discovery mechanisms described in the above-identified patents and patent applications generally apply static discovery thresholds. For example, a minimum number of data flows corresponding to a particular traffic type must be encountered within a given time window for a traffic class to be added to the traffic class configuration. In one implementation, different discovery thresholds can be applied to different traffic types. For example, if a given traffic type is well known, e.g., HTTP, FTP, SMTP, it is added to a traffic class configuration after only one data flow is encountered; otherwise, the threshold can be set to an arbitrary value, for example, eleven uses with not more than one minute between any two uses.
Current traffic discovery mechanisms, however, operate under a one-size-fits-all approach; that is, the same set of discovery thresholds for new traffic class discovery are applied to all units (e.g., traffic monitoring and/or bandwidth management devices) in all configurations, and in all deployment scenarios. In some situations, new traffic classes are not discovered quickly enough; in other situations, where the volume of traffic that flows through the unit is significant, traffic discovery can only be used in short bursts and subsequent cleanup of the resulting traffic class configuration is required to remove the classes in which the network administrator does not have any interest. For example, use of the current automatic traffic discovery mechanisms can create a multitude of noise classes, given the vast array of applications that can potentially traverse a given network. These noise traffic classes can come from false positives, applications that only run once and never again, low level traffic, and applications that are valid but not of interest to the network administrator. Unfortunately, if a network administrator deletes one of these discovered traffic classes it will most likely be rediscovered and again added to the traffic class configuration. The foregoing circumstances can lead to the creation of large, unwieldy traffic classification configurations, or worse yet, the filling of the traffic class configuration memory space such that no further traffic classes (useful or otherwise) can be discovered. Beyond disabling automatic traffic discovery, there is no known solution to this problem in bandwidth management or traffic monitoring devices except to manually reset system variables, based on trial and error, until the traffic discovery unit functions as desired. Indeed, the circumstances described above often requires periodic intervention by the network administrator. For example, an exemplary work flow given current automatic traffic discovery methodologies is as follows: 1) a network administrator turns automatic traffic discovery on, causing the unit to discover traffic classes and add them to a traffic class configuration; 2) the network administrator turns off the automatic traffic discovery mechanism and deletes unwanted traffic classes from the configuration; and 3) the network administrator repeats the above steps as he or she believes necessary.
In light of the foregoing, a need in the art exists for methods, apparatuses and systems that automatically discover network traffic classes, but reduce the need for user intervention. Embodiments of the present invention substantially fulfill this need.